The present disclosure relates to the field of graphical modeling, and more specifically, to polygon meshes.
A polygon mesh is a three dimensional (3D) object composed of one or more polygons. The polygon mesh can share edges to form a 3D patchwork. Polygonal meshes are extensively used in computer graphics and geometric modeling applications. A variety of operations performed on polygon meshes can include Boolean logic, smoothing, simplification, and the like. Operations performed on polygon meshes can include polygon reduction operations.
Polygon reduction lightens an otherwise heavy computing burden associated with representing and manipulating a polygon mesh by reducing a number of polygons in the polygon mesh, while still retaining a useful fidelity to the shape of the original high-resolution version of the 3D geometric solid. Polygon reduction permits several versions of a 3D object to be generated at different levels of detail (LOD). Polygon reduction may substitute n-gons in a polygon mesh with other n-gons having a greater number of vertices. Thus, multiple three vertices n-gons (triangles) may be replaced with a lower number of n-gons having four vertices (quadrilaterals).
Problems may result when performing polygon reduction (and other graphic modeling operations) on polygon meshes having one or more non-planar polygons. One technique for handling non-planar polygons involves vertex adjustments, where vertices of polygons in a polygon mesh are adjusted to maintain a strong match (high or acceptable resolution) with the 3D object being represented, where the adjustments minimizes a quantity of polygons needed in the polygon mesh. Adjustment to positions of vertices in a polygon mesh can result in distortions, where edges of polygons of the polygon mesh imperfectly match. That is, “cracks” appear in the polygon mesh.
Further techniques and algorithms that re-position vertices of a polygon mesh can have somewhat unpredictable results, which vary depending on which point is selected as a starting point (e.g., starting point of a vertex table) of an algorithm that re-positions vertices. This unpredictable behavior can lead to increasing distortions as the polygon mesh is repetitively processed (and altered) by vertices shifting algorithms. In other words, distortions in the polygon mesh continuously increase as the polygon mesh is continuously manipulated.